//题目:
// 给定一个可包含重复数字的整数集合 nums ，按任意顺序 返回它所有不重复的全排列。
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
//代码:
class Solution 
{
    vector<vector<int>> vv;
    vector<bool> arr;
    vector<int> v;
public:
    //法二:
    // bool front_none_same(const vector<int>& nums,const vector<bool>& arr,int tail_pos)
    // {
    //     for(int i=0;i<tail_pos;i++)
    //         if(nums[i]==nums[tail_pos] && arr[i]==true)return false;
    //     return true;
    // }
    // void dfs(const vector<int>& nums,vector<bool> arr,vector<int> v)//这里的arr用的是下标表示数组元素的状态
    // {
    //     if(v.size()==nums.size())
    //     {
    //         vv.push_back(v);
    //         return;
    //     }
    //     for(int i=0;i<nums.size();i++)
    //     {
            
    //         if(arr[i]==false && front_none_same(nums,arr,i))//对应位置没被占用
    //         {
    //             v.push_back(nums[i]);
    //             arr[i]=true;

    //             dfs(nums,arr,v);
    //             //回溯
    //             v.pop_back();
    //             arr[i]=false;
    //         }
    //     }
    // }

    //法三:
    // void dfs(const vector<int>& nums,vector<bool> arr,vector<int> v)
    // {
    //     if(v.size()==nums.size())
    //     {
    //         vv.push_back(v);
    //         return;
    //     }
    //     map<int,bool> buf;//记录这一层被使用过的元素,默认是false
    //     for(int i=0;i<nums.size();i++)
    //     {
    //         if(arr[i]==false && buf[nums[i]]==false)//对应位置没被占用
    //         {
    //             v.push_back(nums[i]);
    //             arr[i]=true;
    //             buf[nums[i]]=true;

    //             dfs(nums,arr,v);
    //             //回溯
    //             v.pop_back();
    //             arr[i]=false;
    //         }
    //     }
    // }

    bool same_level_same_val(const vector<int>& nums,int left,int right)
    {
        if(left<0 || nums[left]!=nums[right] || arr[left]==true)return false;
        return true;
    }
    void dfs(const vector<int>& nums)//这里的arr用的是下标表示数组元素的状态
    {
        if(v.size()==nums.size())
        {
            vv.push_back(v);
            return;
        }
        for(int i=0;i<nums.size();i++)
        {
            
            if(arr[i]==false && same_level_same_val(nums,i-1,i)==false)//对应位置没被占用
            {
                v.push_back(nums[i]);
                arr[i]=true;

                dfs(nums);
                //回溯
                v.pop_back();
                arr[i]=false;
            }
        }
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) 
    {
        sort(nums.begin(),nums.end());
        arr.resize(nums.size(),0);
        dfs(nums);


        //法一:
        // set<vector<int>> st;
        // vector<vector<int>>  ret;
        // for(auto v:vv)
        // {
        //     if(st.find(v)==st.end())
        //     {
        //         st.insert(v);
        //         ret.push_back(v);
        //     }
        // }

        return vv;
    }
};